package leetcode_400;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *@author 周杨
 *SuperUglyNumber_313 给定固定基本素数数组 要求superUglyNumber必须由这些数组成
 *describe:
 *2018年7月2日 下午7:00:46
 */
public class SuperUglyNumber_313 {

	public static void main(String[] args) {
		SuperUglyNumber_313 test=new SuperUglyNumber_313();
		System.out.println(test.nthSuperUglyNumber(12, new int[]{2,7,13,19}));

	}
	/**
	 * describe:采取上一题的思想 用多队列实现 AC 8%
	 * 2018年7月2日 下午7:04:03
	 */
	public int nthSuperUglyNumber(int n, int[] primes) {
        if(n==1)
        	return 1;
        List<Queue<Integer>> help=new ArrayList<Queue<Integer>>();
        for(int i:primes) {
        	Queue<Integer> queue=new LinkedList<Integer>();
        	queue.add(i);
        	help.add(queue);
        }
        int count=1;//level记录最小数在哪一个
        while(count<n) {
        	int min=Integer.MAX_VALUE;
        	for(int i=0;i<help.size();++i) {
        		int now=help.get(i).peek();
        		min=Math.min(min, now);
        	}
        	for(int i=0;i<help.size();++i) {
        		int now=help.get(i).peek();
        		if(now==min)
        			help.get(i).poll();
        	}
        	if(count+1==n)
        		return min;
        	++count;
        	System.out.println(min);
        	for(int i=0;i<help.size();++i) {
        		help.get(i).add(primes[i]*min);
        	}
        	
        }
        return -1;
    }
	
	/**
	 * describe:相同思想 用index代表下标 也代表队列头 AC 60%
	 * 2018年7月2日 下午7:20:34
	 */
	public int nthSuperUglyNumber1(int n, int[] primes) {
		int[] dp = new int[n];
		// 第一个超级丑数是1
		dp[0] = 1;
		int[] idxPrimes = new int[primes.length];
		int counter = 1;
		while (counter < n) {
			int min = Integer.MAX_VALUE;
			for (int i = 0; i < primes.length; i++) {
				// idxPrimes[i]代表每个丑数的个数，
				// 比如丑数2题目的2，3，5，
				// idxPrimes[0]代表2的下标
				// idxPrimes[1]代表3的下标
				// idxPrimes[2]代表5的下标
				int temp = dp[idxPrimes[i]] * primes[i];
				min = min < temp ? min : temp;
			}
			// 如果min和 dp[idxPrimes[i]] * primes[i]相等，
			// 则其对应的下标++
			for (int i = 0; i < primes.length; i++) {
				if (min == dp[idxPrimes[i]] * primes[i]) {
					idxPrimes[i]++;
				}
			}
			dp[counter] = min;
			counter++;
		}
		return dp[n - 1];
	}

}
